#-------------------------------------------------------------------------------
# Name:        module1
# Purpose:      AI to make moves in connect 4 game
#
# Author:      mcki4229
#
# Created:     05/03/2012
# Copyright:   (c) mcki4229 2012
# Licence:     <your licence>
#-------------------------------------------------------------------------------
#!/usr/bin/env python
from connect4board import *
from random import random, randint
import copy

DLIM = 3 #Depth limit for minmax tree
#Minmax algorithm
#Tree for minmax algorithm
class minMaxNode(object):
    """Node for gameboard searching. Forms a tree of nodes with a branching factor of 7"""
    children = []
    value = 0
    thisBoard = Board() #store manipulations of board

    def __init__(self, gameBoard, currentPlayer, minormax, depth):
        #currentPlayer is 'X' or 'O'
        #minormax is either 'min' or 'max'
        #depth is the root of the node. Parent node is depth 0, first child is 1, etc.
        if depth == DLIM:
            self = None #Why? Maybe to stop the recursive constructor
            return

        self.thisBoard = copy.deepcopy(gameBoard)

        if currentPlayer == 'X':
            nextPlayer = 'O'
        if currentPlayer == 'O':
            nextPlayer = 'X'
        if minormax == 'min':
            nextminormax = 'max'
        if minormax == 'max':
            nextminormax = 'min'

        #7 children to represent the game state in subsequent moves choosing a column 0-6
        # Make the move and store as new board state
        childrenBoards = [copy.deepcopy(gameBoard) for i in range(7)]
        for i in range(7):
            childrenBoards[i].playMove(currentPlayer, i)
##            if depth == 1:
##                print "Board DEBUG7: ", i
##                childrenBoards[i].printBoard()
##                print minormax
##                print currentPlayer

        #update array of children minMaxNodes
        self.children = [minMaxNode(childrenBoards[i], nextPlayer, nextminormax, depth+1) for i in range(7)]


def minMaxValue(node, level, currentPlayer, minormax, gameBoard):
    """Returns (index,value) of node in a tuple. Index corresponds to the slot 0-6
    node is of type minMaxNode
    """

    if currentPlayer == 'X':
        nextPlayer = 'O'
    if currentPlayer == 'O':
        nextPlayer = 'X'
    if minormax == 'min':
        nextminormax = 'max'
    if minormax == 'max':
        nextminormax = 'min'

    if level >= DLIM: #Return the heuristic after reaching the minmax depth limit
        dummyindex = 0
        heuristicValue = heuristic(currentPlayer, minormax, node.thisBoard)
        node.value = heuristicValue
        return (dummyindex, heuristicValue) #because each child calls the heuristic function, index is not relevant but the value of that position is

    #if it is min's turn to evaluate, grab the lowest value,
    if minormax == 'min':
        indexAndValues = ([minMaxValue(node.children[i],level+1,nextPlayer,nextminormax,node.children[i].thisBoard) for i in range(7)])
        values = [val for (ind,val) in indexAndValues]

        for i in range(7): #assign values to nodes
            node.children[i].value = values[i]

        node.thisBoard.printBoard()
        print "Values: " , ["%.2f" % v for v in values]
        min_value = min(values)
        min_index = values.index(min_value)
        print "Min index: ", min_index
        print "Min value: " , "%.2f" %  min_value
        node.value = min_value
        return (min_index, min_value)

    #if it is max's turn to evaluate, grab the highest value
    if minormax == 'max':
        indexAndValues = ([minMaxValue(node.children[i],level+1,nextPlayer,nextminormax,node.children[i].thisBoard) for i in range(7)]) #returns a list of tuples (index, value)
        values = [val for (ind,val) in indexAndValues]

        for i in range(7): #assign values to nodes
            node.children[i].value = values[i]

        node.thisBoard.printBoard()
        print "Values: " , ["%.2f" % v for v in values]
        max_value = max(values)
        max_index = values.index(max_value)
        print "Max index: ", max_index
        print "Max value: " , "%.2f" % max_value
        node.value = max_value
        return (max_index, max_value)

def print_tree_indented(node, level=0):
    """Print the Tree in a slightly more intuitive format (sideways)"""
    if level >= DLIM:
        return
    for i in [6,5,4]:
        print_tree_indented(node.children[i], level+1)
    print '    ' * level + "%.2f" % (node.value)
    for i in [3,2,1,0]:
        print_tree_indented(node.children[i], level+1)

#eval heuristic
def heuristicFunctionSimple(currentPlayer, minormax, gameBoard):
    """Stub Heuristic: Return random value"""
    r = random()*2-1 #Random number between -1,1
    return r

def heuristic(currentPlayer, minormax, gameBoard):
    """evaluation heuristic
    @currentPlayer 'X' or 'O'
    @minormax "min" or "max"
    @gameBoard pointer to Board() instance


    """
    #1000 pts for win for current player
    #100 pts for 3 in a row
    #10 pts for 2 in a row
    #1 pt for 1
    #-1 for other player (non current) 1
    #-1 for opponent
    #-10 for opponent ... etc

    #really easy heuristic to stub. Give a 1000 points for 4 in a row, 0 if other
    if currentPlayer == 'X':
        otherPlayer = 'O'
    if currentPlayer == 'O':
        otherPlayer = 'X'

    #debug board state
    gameBoard.printBoard()
    print "This is the board passed to the Heuristic"
    print "winCheck() = ", gameBoard.winCheck()

    #******

    if gameBoard.winCheck() == currentPlayer:
        print "DEBUG3"
        return 1000
    if gameBoard.winCheck() == otherPlayer:
        print "DEBUG4"
        return -1000
    #return 2 #Just a test value

    #return random value if win is not in sight
    return heuristicFunctionSimple(currentPlayer, minormax, gameBoard)

def Move(currentPlayer, gameBoard):
    """AI determines move using searching + heuristic evaluation function
    assume currentPlayer coming in correctly as 'X' or 'O' ~~ taken care of in main
    """

    #Make parent root node and subsequent node structure
    rootNode = minMaxNode(gameBoard, currentPlayer, 'max', 0) #root node always chooses max, current depth level is 0

    #Return index (column choice) and value of that choice using minmax
    (index,val) = minMaxValue(rootNode,0, currentPlayer, 'max', gameBoard)
    print "Trying Move Choice...: ", index
    move = gameBoard.playMove(currentPlayer, index)
    if move == 'legal':
        print "Legal move taken: ", index
    if move == 'illegal':
        print "something went wrong"
        print "Going with random move"
        randMove(currentPlayer, gameBoard)
    return

def randMove(currentPlayer,gameBoard):
    """Stub move: AI chooses random legal move"""
    while (1):
        r = randint(0,6)
        print "Trying Move Choice...: ", r
        move = gameBoard.playMove(currentPlayer,r)
        if move == 'legal':
            print "Legal move taken: ", r
            return

def main():
    gameBoard = Board()


#```````````
#Set up easy test case for heuristic function
    for i in range(3):
        gameBoard.board[5-i][0] = 'X'
        gameBoard.board[5-i][3] = 'O'
##    gameBoard.board[2][0] = 'X'
    gameBoard.printBoard()

#```````````

    a = minMaxNode(gameBoard, 'X', 'max', 0)

    (i,val) = minMaxValue(a, 0, 'X', 'max', gameBoard)
    #print_tree_indented(a,0)
    print "Value of node a: ", "%.2f" % val
    print "Index chosen at a: ", i
    print "done"

    for i in range(7):
        print "Children of root value: ", a.children[i].value, i
    for i in range(7):
        print "Children of child 0 of root: ", a.children[0].children[i].value, i
    print "Value of root node: ", a.value
    print "Top level board"
    a.thisBoard.printBoard()
    print "1st child"
    a.children[0].thisBoard.printBoard()
    print a.children[0].value

    print gameBoard.winCheck()
    gameBoard.board[2][0] = 'X'
    print gameBoard.winCheck()




if __name__ == '__main__':
    main()
